import time

class Tweet:
    def __init__(self, t, tid):
        self.time = t
        self.tid = tid

class User:

    def __init__(self):
        self.followees = set()
        self.tweets = []
        self.lastTweet = -1

    def tweet(self, tid):
        self.tweets.append(Tweet(time.clock(), tid))

    def follow(self, followee):
        if followee!=self:
            self.followees.add(followee)
    
    def unfollow(self, followee):
        if followee in self.followees:
            self.followees.remove(followee)

    def getFeeds(self):
        feeds = []
        for followee in self.followees: followee.reset()
        self.reset()
        for _ in range(10):
            lastTweet = Tweet(0, 0)
            lastFollowee = None
            for followee in self.followees:
                tweet = followee.getLastTweet()
                if tweet != None and tweet.time > lastTweet.time:
                    lastTweet = tweet
                    lastFollowee = followee
            tweet = self.getLastTweet()
            if tweet != None and tweet.time > lastTweet.time:
                lastTweet = tweet
                lastFollowee = self
            if lastFollowee != None:
                feeds.append(lastTweet.tid)
                lastFollowee.decrease()
            else:
                break
        return feeds

    def reset(self):
        self.tweets.sort(key=lambda tweet: tweet.time)
        self.lastTweet = len(self.tweets)-1

    def getLastTweet(self):
        if self.lastTweet<0: return None
        else: return self.tweets[self.lastTweet]
    
    def decrease(self):
        self.lastTweet -= 1

class Twitter(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.userDict = {}

    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        if userId not in self.userDict:
            self.userDict.update({userId:User()})
        self.userDict[userId].tweet(tweetId)

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        if userId not in self.userDict: return []
        else: return self.userDict[userId].getFeeds()

    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId not in self.userDict:
            self.userDict.update({followerId:User()})
        if followeeId not in self.userDict:
            self.userDict.update({followeeId:User()})
        followee = self.userDict[followeeId]
        self.userDict[followerId].follow(followee)

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        if followerId not in self.userDict:
            self.userDict.update({followerId:User()})
        if followeeId not in self.userDict:
            self.userDict.update({followeeId:User()})
        followee = self.userDict[followeeId]
        self.userDict[followerId].unfollow(followee)

twitter = Twitter()
twitter.postTweet(1, 5)
print(twitter.getNewsFeed(1))
twitter.follow(1, 2)
twitter.postTweet(2, 6)
print(twitter.getNewsFeed(1))
twitter.unfollow(1, 2)
print(twitter.getNewsFeed(1))